package com.lagou.man;

/**
 * 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。
 * 例如有的金矿储量是500kg黄金，需要5个工人来挖掘；
 * 有的金矿储量是200kg黄金，需要3个工人来挖掘……
 * 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。
 * 要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
 *
 * @author zyt
 * @since 2021/1/14 22:20
 */
public class GetBestGoldIncomeTask {

    public static void main(String[] args) {
        int w = 10;
        int[] p = {5, 5, 3, 4, 3};
        int[] g = {400, 500, 200, 300, 350};
        System.out.println("最优收益为：" + getBestGoldIncome(w, p, g));
    }

    /**
     * 具体解法分析：
     * 金矿数---> n(用g.length表示)
     * 工人数---> w
     * 每个金矿的含金量数组---> g[]
     * 每个金矿所需挖矿工人数---> p[]
     * F(n,w) ---> n个金矿，w个工人时的最佳收益函数
     *
     * 转化函数式：
     * F(n,w)=0 (n=0 或者  w=0)
     * F(n,w)=F(n-1,w) (n>=1, w<p[n-1])
     * F(n,w)=Math.max(F(n-1,w), F(n-1, w-p[n-1])+g[n-1]) (n>=1, w>=p[n-1])
     *
     *
     * 获得金矿最优收益
     * @param w 工人数量
     * @param p 金矿开采所需的工人数量
     * @param g 每个金矿的含金量数组
     * @return 最优收益
     */
    public static int getBestGoldIncome(int w, int[] p, int[] g){
        int[][] result=new int[g.length+1][w+1];

        for(int i=1; i<=g.length; i++) {
            for(int j=1; j<=w; j++) {
                if(j<p[i-1]) {
                    result[i][j]=result[i-1][j];
                }
                else
                {
                    result[i][j]=Math.max(result[i-1][j], result[i-1][j-p[i-1]]+g[i-1]);
                }
            }
        }
        return result[g.length][w];
    }
}